package LK_Data_Structure;

import java.util.*;

public class DataS_Day_4 {
    /*. 重塑矩阵
    * 重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
    * 解题思路:1:使用映射关系
    * 2:使用哈希表*/

    public static int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length, n = mat[0].length, x = 0;
        if(m * n != r * c) return mat;
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                hash.put(x++, mat[i][j]);
            }
        }
        int[][] newMat = new int[r][c];
        for(int i = 0; i < r; ++i){
            for(int j = 0; j < c; ++j){
                newMat[i][j] = hash.get(i*c + j);
            }
        }
        return newMat;
    }

    /*给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
    在「杨辉三角」中，每个数是它左上方和右上方的数的和。*/
    public List<List<Integer>> generate(int numRows) {
        //杨辉三角写法
        //   ArrayList是顺序表;
        List<List<Integer>> ret=new ArrayList<>();
        //构建一个二维数组
        List<Integer> row=new ArrayList<>();//第一行
        row.add(1);
        ret.add(row);//将第一行放进去
        for (int i = 1; i < numRows; i++) {
            //杨辉三角的第二行开始
            List<Integer> pveroe=ret.get(i-1);//获取上一行
            List<Integer> roe=new ArrayList<>();
            roe.add(1);//第一个元素置为1

            for (int j = 1; j < i; j++) {
                //每行的第一个元素和最后一个元素为1
                int x= pveroe.get(j)+pveroe.get(j-1);
                roe.add(x);
            }
            roe.add(1);//最后一个元素置为1
            ret.add(roe);
        }
        return ret;
    }
}
